package oj.oj_138;
/**
 * 复制带随机指针的链表
 */

import java.util.Comparator;
import java.util.TreeMap;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class Solution {
    /*
    目前缺少一个映射关系
    Node@501(老 7) -> Node@508(新 7)
    老 13 -> 新 13
    老 -> 新
     */
    public Node copyRandomList(Node head) {
        Node fakeHead = new Node(-1);
        Node last = fakeHead;

        TreeMap<Node, Node> map = new TreeMap<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                // 只是需要比较能力，谁大谁小，不关心，只要不变
                return o1.hashCode() - o2.hashCode();
            }
        });

        Node cur = head;
        while (cur != null) {
            int val = cur.val;
            Node node = new Node(val);
            // cur -> node
            map.put(cur, node);



            node.random = cur.random;   // BUG: 浅拷贝

            // 尾插
            last.next = node;
            last = node;

            cur = cur.next;
        }

        Node newCur = fakeHead.next;
        while (newCur != null) {
            if (newCur.random != null) {
                // newCur.random 指向的是老链表中结点，比如是 11
                // map.get(newCur.random) 拿到新链表中的结点，还是 11
                // newCur.random = 新结点
                Node oldNode = newCur.random;
                Node newNode = map.get(oldNode);
                newCur.random = newNode;
            }
            newCur = newCur.next;
        }

        return fakeHead.next;
    }

    public static void main(String[] args) {
        Node n1 = new Node(7);
        Node n2 = new Node(13);
        Node n3 = new Node(11);
        Node n4 = new Node(10);
        Node n5 = new Node(1);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        n1.random = null;
        n2.random = n1;
        n3.random = n5;
        n4.random = n3;
        n5.random = n1;

        Node head = n1;

        Solution solution = new Solution();
        Node ans = solution.copyRandomList(head);
    }
}
